#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
struct ListNode {
    int val;
    struct ListNode* next;
};


struct ListNode* findMid(struct ListNode* phead)
{
    struct ListNode* slow = phead, * fast = phead;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
struct ListNode* reserve(struct ListNode* phead)
{
    if (phead == NULL)
    {
        return NULL;
    }
    struct ListNode* newhead = NULL;
    struct ListNode* cur = phead;
    while (cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}
bool chkPalindrome(struct ListNode* phead) {
    struct ListNode* mid = findMid(phead);
    struct ListNode* midPhead = reserve(mid);
    while (phead && midPhead)
    {
        if (phead->val != midPhead->val)
            return false;
        phead = phead->next;
        midPhead = midPhead->next;
    }
    return true;
}

int main()
{
    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));

    n1->val = 1;
    n2->val = 2;
    n3->val = 2;
    n4->val = 1;

    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = NULL;
    bool out = chkPalindrome(n1);
    return 0;
}